package com.freedy.dataStructure.tree;

import org.w3c.dom.Node;

import java.util.StringJoiner;

/**
 * @author Freedy
 * @date 2021/3/23 19:50
 */
public class BinaryTree<T> {
    private final Node<T> root;
    private Node<T> temp;
    private Node<T> last;

    public BinaryTree(T data) {
        root = new Node<>();
        root.setData(data);
        temp = root;
        last = root;
    }

    public BinaryTree(Node<T> root) {
        this.root = root;
        temp = root;
        last = root;
    }

    /**
     * 向左插入，并且下一次操作是以你现在插入的那个为准
     */
    public BinaryTree<T> putLeft(T data) {
        last = temp;
        Node<T> node = new Node<>();
        node.setData(data);
        temp.setLeftNode(node);
        temp = node;
        return this;
    }

    /**
     * 向有插入，并且下一次操作是以你现在插入的那个为准
     */
    public BinaryTree<T> putRight(T data) {
        last = temp;
        Node<T> node = new Node<>();
        node.setData(data);
        temp.setRightNode(node);
        temp = node;
        return this;
    }

    /**
     * 让插入标准 回到root
     */
    public BinaryTree<T> returnRoot() {
        temp = root;
        return this;
    }

    /**
     * 让插入标准 回到上次操作
     */
    public BinaryTree<T> returnLast() {
        temp = last;
        return this;
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        if (root != null) root.preOrder();
    }

    /**
     * 中续遍历
     */
    public void infixOrder() {
        if (root != null) root.infixOrder();
    }

    /**
     * 后续遍历
     */
    public void postOrder() {
        if (root != null) root.postOrder();
    }

    /**
     * 判断树是否包含某个节点
     */
    public Boolean contain(T data) {
        return root.search(data);
    }

    /**
     * 删除树上的某个节点,并且连同该节点的子树
     */
    public Boolean del(T data) {
        if (root.data.equals(data)) return true;
        return root.deleteNode(data);
    }

    public static class Node<T> {
        private T data;
        private Node<T> leftNode;
        private Node<T> rightNode;

        public Node(T data, Node<T> leftNode, Node<T> rightNode) {
            this.data = data;
            this.leftNode = leftNode;
            this.rightNode = rightNode;
        }

        public Node(T data) {
            this.data = data;
        }

        public Node(Node<T> leftNode, Node<T> rightNode) {
            this.leftNode = leftNode;
            this.rightNode = rightNode;
        }

        public Node() {
        }

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public Node<T> getLeftNode() {
            return leftNode;
        }

        public void setLeftNode(Node<T> leftNode) {
            this.leftNode = leftNode;
        }

        public Node<T> getRightNode() {
            return rightNode;
        }

        public void setRightNode(Node<T> rightNode) {
            this.rightNode = rightNode;
        }

        @Override
        public String toString() {
            return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]")
                    .add("data=" + data)
                    .toString();
        }

        /**
         * 前中后序遍历
         */
        public void preOrder() {
            System.out.println(this);
            if (leftNode != null) {
                leftNode.preOrder();
            }
            if (rightNode != null) {
                rightNode.preOrder();
            }
        }

        public void infixOrder() {
            if (leftNode != null) {
                leftNode.infixOrder();
            }
            System.out.println(this);
            if (rightNode != null) {
                rightNode.infixOrder();
            }
        }

        public void postOrder() {
            if (leftNode != null) {
                leftNode.postOrder();
            }
            if (rightNode != null) {
                rightNode.postOrder();
            }
            System.out.println(this);
        }

        public boolean search(T data){
            if (this.data.equals(data)) return true;
            if (leftNode != null) {
                boolean left = leftNode.search(data);
                if (left) return true;
            }
            if (rightNode != null) {
                return rightNode.search(data);
            }
            return false;
        }

        public Boolean deleteNode(T data) {
            if (leftNode!=null&&leftNode.getData().equals(data)){
                leftNode=null;
                return true;
            }
            if (rightNode != null&&rightNode.getData().equals(data)) {
                rightNode=null;
                return true;
            }
            if (leftNode != null) {
                boolean left = leftNode.deleteNode(data);
                if (left) return true;
            }
            if (rightNode != null) {
                return rightNode.deleteNode(data);
            }
            return false;
        }

    }
}
